package day33_719_other822;

import java.util.*;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/11 20:10
 * @Version 1.0
 */
public class Solution {
    public int solve(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1] - nums[0];
        while (l <= r) {
            int mid = (l + r) / 2;
            if (countNotGreater(nums, mid) <= k) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }

    private long countNotGreater(int[] nums, int diff) {
        int i = 0;
        long ans = 0;
        for (int j = 1; j < nums.length; j++) {
            while (nums[j] - nums[i] > diff) {
                i++;
            }
            ans += (j - i);
        }
        return ans;
    }
}
